class Solution {
public:
    vector<int> rearrangeBarcodes(vector<int>& barcodes) {
        int max_value = *max_element(barcodes.begin(), barcodes.end());
        int hash[max_value + 1];
        memset(hash, 0, sizeof(hash));
        for(int &x : barcodes)
            hash[x]++;
        
        // 大堆
        priority_queue<pair<int, int>> pq;
        for(int i = 0; i <= max_value; i++)
            if(hash[i] > 0)
                pq.emplace(hash[i], i);     // <freqence, value>

        vector<int> ret;
        while(!pq.empty())
        {
            auto [freq, value] = pq.top();
            pq.pop();

            // 如果和ret数组最后一个元素不相同 or 刚开始的情况(ret.size() == 0)
            if(ret.size() == 0 || value != ret.back())
            {
                ret.push_back(value);
                if(--freq)
                    pq.emplace(freq, value);
            }
            // 如果和ret数组末尾元素相等
            else
            {
                // 继续取此时堆顶元素，必然是出现频率次大的元素
                auto [f, v] = pq.top();
                pq.pop();

                ret.push_back(v);
                if(--f)
                    pq.emplace(f, v);
                
                // 由于刚开始的堆顶元素和末尾元素相同，所以需要重新入堆
                pq.emplace(freq, value);
            }
        }
        return ret;
    }
};